Last years have witnessed spectacular developments of wireless networks that have widely transformed all aspects of modern societies. Driven by the emergence of new real-time high-throughput multimedia applications and the success of digital technologies, several network solutions are available today and are thoroughly used in all modes of communications. Main examples include cellular networks, wireless ad-hoc networks and wireless sensor networks involving single or multiple users and/or antennas. In order to ensure a reliable Quality of Service (QoS) in such communication systems, efficient physical layer technologies are needed. Particularly, in order to provide high-rate and reliable transmission, robust and low-complexity decoding algorithms need to be implemented at the receiver devices.
Optimal decoding performance are obtained using the Maximum Likelihood (ML) decoding technique according to which the receiver device is configured to estimate the likeliest candidate signal, given the observed received signal. Optimal ML decoding technique relies on counting all the possible transmitted signals (also referred to as “candidate signals”), and selecting the likeliest signal according to selection criteria, such as the minimization of the Euclidean distance between the received signal and the candidate signals.
Such ML decoding techniques use an exhaustive search and provide optimal performance. However, they require a high complexity that increases as the size of the constellation codebook or the number of the transmit antennas becomes higher, thereby making the implementation of such techniques impossible in practical systems.
In order to reduce the decoding complexity of ML decoding, tree-search based decoders have been proposed which explore a tree-structured search space to determine the closest vector to the received signal vector, such as the lattice spherical decoders (also known as “Sphere Decoders”). Sphere decoders implement a tree search to search lattice points within a sphere defined by a radius and centered at the received signal.
Sphere decoders were initially disclosed in the articles:
“A universal lattice code decoder for fading channels”, IEEE Trans. Inform. Theory, vol. 45, pp. 1639-1642, July, 1999 by E. Viterbo and J. Boutros, and
“Lattice code decoder for space-time codes”, IEEE Communications Letters, 4(5):161-163, May 2000 by O. Damen, A. Chkeif, and J-C. Belfiore.
According to such sphere decoding methods, the ML solution is sought inside a sphere of a predefined radius centered at the received point. The sphere decoding method explores the tree of all possible lattice points and uses a path metric in order to discard paths corresponding to points outside the search sphere. In certain conventional sphere decoding methods, the initial radius of the search sphere is chosen from the noise variance. Limiting the search space to the spherical region allows a reduction of the number of visited points. These types of decoders are particularly adapted to wireless communications involving both single and multiple antennas as well as to optical communications. However, the complexity of these types of decoder increases with increasing constellation size or increasing number of antennas.
Alternative decoding techniques have been proposed such as sequential decoding techniques (also known as “stack” decoding techniques) which are based on a tree representation of the ML optimization problem (decoding tree) and on a tree search according to a Best-First strategy. Such sequential decoding techniques further use a stack to store the best candidate lattice points. In the decoding tree, each path from the root node to a leaf node is a possible transmitted signal. Nodes in the search tree correspond to different values taken by the decoded symbols and each path from the root node to a leaf node represents a possible transmitted signal.
Sequential decoding techniques take into account a cost (or metric) associated with the nodes of the decoding tree in order to determine a single candidate path inside a decoding tree by assigning a cost to each current node, such as the Euclidean distance between the signal received and the symbols vector represented by the path between the root node and the current node. The search tree is no longer binary and contains the different possible values of the information symbols.
Stack decoders improve the overall decoding complexity. However, for an increasing constellation size and a high number of antennas, the stack decoding technique requires a high computational complexity. In order to reduce this complexity, still another decoding technique referred to as the Spherical-Bound Stack decoder (SB-Stack) has been proposed in the article by G. R. Ben-Othman, R. Ouertani, and A. Salah, entitled “The Spherical Bound Stack Decoder”, In Proceedings of International Conference on Wireless and Mobile Computing, pages 322-327, October 2008. The SB-stack approach combines the Stack search strategy with the Sphere Decoder search region: the decoder searches for the closest point inside a sphere centered at the received point implementing the stack decoding strategy. The spherical search region imposes a search interval for each decoded symbol. Only nodes belonging to these intervals at each tree level are visited and expanded. Limiting the search space to a spherical region allows the SB-Stack decoder to offer ML performance with a complexity reduction of at least 30% over the Sphere Decoder. However, although the SB-stack decoder offers lower complexity than the Sphere Decoder, its implementation in practical systems requires high storage capacities.
In conventional decoders implementing a tree search of the closest vector in a sphere space, such as sphere decoders or SB-Stack decoders, the computational complexity depends critically on the choice of the initial sphere radius. Accordingly, a main issue of such decoders is the selection of the sphere radius initially set to initiate the search of candidate lattice points. Specifically, to include at least one lattice point inside the sphere, the initial radius is required to be large enough. In contrast, a smaller initial radius shall be preferred to avoid an exponential search as a too large radius fosters the presence of many lattice points inside the sphere. Accordingly, a relevant trade-off shall be found between a large-enough initial radius for ensuring that at least one lattice point is included inside the sphere and a small-enough radius to optimize the computational complexity and greatly speed up the decoder.
Several methods have been proposed to select the initial radius. In one approach, the covering radius of the lattice generated by the channel matrix is considered as the initial radius. In still another approach, an upper bound of the covering radius is used as further disclosed in the article “A universal decoding algorithm for lattice codes”, In Quatorzieme colloque GRETSI, 1993, by E. Viterbo and E. Biglieri. However, such selection methods based on the cover radius or the upper bound suffer from high computational complexity as an increasing number of lattice points are visited.
In yet another approach, the initial sphere radius can be selected taking into account the statistical characteristics of the noise power as disclosed in “Sphere decoding algorithms with improved radius search”, Proceedings of IEEE Transactions by on Communications, 53(7):1104-1109, July 2005 BY W. Zhao and G. B. Giannakis. One major drawback of this method for initial radius selection is that it generates an increase of the initial radius. Indeed, when the initial radius is too small to succeed in searching at least one lattice point inside a sphere having the initial radius, the radius is increased until at least one lattice point is found inside the sphere.
Further, with such approaches, the number of lattice points included inside the sphere increases as the radius increases so that too many lattice points can be included inside the sphere, which greatly increases the decoder complexity.
Yet another solution for selecting the initial radius is based on considering the Euclidean distance between the received signal and the Zero Forcing estimate (also called the Babai estimate), as described in US2008/0313252 or in the article “On the expected complexity of sphere decoding”, In Proceedings of Asilomar Conference on Signals, Systems and Computers, volume 2, pages 1051-1055, November 2001 by B. Hassibi and H. Vikalo. This ensures that the ZF estimate and at least one lattice point are included inside the sphere. However, this solution suffers from high computational complexity.
However, although the selection of the initial radius with such methods ensures that a plurality of lattice points are included within a sphere having the initial radius, the initial radius may be still too large thereby increasing the computational complexity of the decoder.